정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
K개의 점 데이터를 포함하는 최소 BR 탐색 |
| 영문제목(English Title) |
Finding the Minimum MBRs Embedding K Points |
| 저자(Author) |
김건우
김영훈
Keonwoo Kim
Younghoon Kim
|
| 원문수록처(Citation) |
VOL 44 NO. 01 PP. 0071 ~ 0077 (2017. 01) |
한글내용
(Korean Abstract) |
스마트폰과 같은 GPS센서가 장착된 모바일 기기가 널리 보급되고 있다. 이러한 추세에 따라 트위터나 페이스북과 같은 소셜 미디어에서 GEO태그가 된 메시지 (즉, GPS 위치를 갖는 멀티미디어 메시지)를 손쉽게 작성할 수 있게 되었고 게시자의 위치 정보를 포함하는 공간 데이터가 급증하고 있다. 그러나 이러한 공간 데이터에서 항상 위치 정보와 게시글 내용이 명시적인 연관성을 갖고 있지는 않다. 때문에 키워드와 위치 정보 분포의 관련성에 따라 검색 결과를 재구성 할 필요가 있다. 우리는 크기가 가장 작은 k개의 점 데이터를 포함하는 최소 경계사각형(MBR)을 찾음으로써 데이터가 가장 밀집된 사각형을 찾으며, 이는 위치 검색 시스템에서 유용하게 사용될 수 있다. 본 논문은 최소 경계 사각형과 같이 거리가 가까운 2차원 공간 데이터의 묶음을 찾기 위해 효율적인 알고리즘을 제안하였고 합성 데이터와 실제 데이터를 이용한 실험을 통해 알고리즘의 효율성을 검증하였다.
|
영문내용
(English Abstract) |
There has been a recent spate in the usage of mobile device equipped GPS sensors, such as smart phones. This trend enables the posting of geo-tagged messages (i.e., multimedia messages with GPS locations) on social media such as Twitter and Facebook, and the volume of such spatial data is rapidly growing. However, the relationships between the location and content of messages are not always explicitly shown in such geo-tagged messages. Thus, the need arises to reorganize search results to find the relationship between keywords and the spatial distribution of messages. We find the smallest minimum bounding rectangle (MBR) that embedding k or more points in order to find the most dense rectangle of data, and it can be usefully used in the location search system. In this paper, we suggest efficient algorithms to discover a group of 2-Dimensional spatial data with a close distance, such as MBR. The efficiency of our proposed algorithms with synthetic and real data sets is confirmed experimentally.
|
| 키워드(Keyword) |
공간데이터프로세싱
k데이터포인트포함최소사각형탐색
분할정복알고리즘
시간복잡도분석
spatial data processing
finding k-point embedding minimum box
divide and conquer
time complexity analysis
|
| 파일첨부 |
PDF 다운로드
|
